# 子数组最大平均数I: https://leetcode-cn.com/problems/maximum-average-subarray-i/solution/


# 1. 自己的写法，我企图把窗口扩大再到滑动写到一起~~，不太好
class Solution:
    def findMaxAverage(self, nums: list, k: int) -> float:
        """
            连续子数组，并且长度为 k， 那么就定义双指针，长度为 k，遍历所有子数组即可
            注意： 窗口大小是 i 到 j 闭区间！
        """
        i, j, n = 0, 0, len(nums)

        maxAvg = -1 * 1000000000
        total = 0 
        # 先算出来一次
        while j < n:
            # 先加入元素， 因为闭区间，默认 i = j = 0, 那么应该先含有一个元素再进行，窗口判断
            total += nums[j]        
            # 窗口等于k长度， 计算平均值
            if j - i == k - 1:
                maxAvg = max(maxAvg, total / k)
            # 窗口大于 k长度，往前滑动
            elif j - i > k - 1:
                total -= nums[i]
                i += 1
                maxAvg = max(maxAvg, total / k)

            j += 1
        
        return maxAvg



# 2. 应该先确定好窗口， 循环里直接是滑动
class Solution:
    def findMaxAverage(self, nums: list, k: int) -> float:
        """
            连续子数组，并且长度为 k， 那么就定义双指针，长度为 k，遍历所有子数组即可
            注意： 窗口大小是 i 到 j 闭区间！
        """
        i, j, n = 0, 0, len(nums)
        total = 0 
        # 计算窗口
        for j in range(0, k):
            total += nums[j]
        # 计算第一次平均值
        maxAvg = total / k
        # 滑动窗口
        j += 1
        while j < n:
            total += nums[j]        
            total -= nums[i]
            maxAvg = max(maxAvg, total / k)
            i += 1
            j += 1
        
        return maxAvg

# 官方题解
class Solution:
    def findMaxAverage(self, nums: list, k: int) -> float:
        maxTotal = total = sum(nums[:k])
        n = len(nums)

        for i in range(k, n):
            total = total - nums[i - k] + nums[i]
            maxTotal = max(maxTotal, total)
        
        return maxTotal / k


# 改进写法，少做计算。 求最大和，最后再求平均值
class Solution:
    def findMaxAverage(self, nums: list, k: int) -> float:
        """
            连续子数组，并且长度为 k， 那么就定义双指针，长度为 k，遍历所有子数组即可
            注意： 窗口大小是 i 到 j 闭区间！
        """
        i, j, n = 0, 0, len(nums)
        total = 0 
        # 计算窗口
        for j in range(0, k):
            total += nums[j]
        maxTotal = total
        # 滑动窗口
        j += 1
        while j < n:
            total += nums[j]        
            total -= nums[i]
            maxTotal = max(maxTotal, total)
            i += 1
            j += 1
        
        return maxTotal / k


# 还可以使用前缀和 解法